๐Ÿ‘ฉโ€๐Ÿ’ป 72413. ํ•ฉ์Šน ํƒ์‹œ ์š”๊ธˆ

@Seongukbaek Posted July 02, 2022 ยท Updated July 02, 2022 ยท 4 min read

๋ฌธ์ œ

Programmers - ํ•ฉ์Šน ํƒ์‹œ ์š”๊ธˆ

๐Ÿ“ Logic

private static int[] dijkstra(int start) { int[] costs = new int[n + 1]; Arrays.fill(costs, Integer.MAX_VALUE); Queue<Edge> queue = new PriorityQueue<>(); queue.add(new Edge(start, 0)); costs[start] = 0; while(!queue.isEmpty()) { Edge node = queue.poll(); int now = node.dest; int weight = node.weight; // ํ˜„์žฌ ๋น„์šฉ๋ณด๋‹ค ๋” ํฐ ๊ฒฝ์šฐ๋Š” ํŒจ์Šค if (weight > costs[now]) continue; // ํ˜„์žฌ ์ •์ ์—์„œ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์—ฃ์ง€ ๋ฆฌ์ŠคํŠธ ArrayList<Edge> edges = adjList[now]; for (Edge e : edges) { // ํ˜„์žฌ(now) ์ •์ ๊นŒ์ง€์˜ ๋น„์šฉ๊ณผ ๋‹ค์Œ์œผ๋กœ ์ด๋™ํ•  ์—ฃ์ง€์˜ ๋น„์šฉ์˜ ํ•ฉ int cost = costs[now] + e.weight; // ์ด์ „ ๋น„์šฉ๋ณด๋‹ค ์ƒˆ๋กœ์šด ๋น„์šฉ์ด ๋” ์ž‘์€ ๊ฒฝ์šฐ ๊ฐฑ์‹  if (cost < costs[e.dest]) { costs[e.dest] = cost; queue.add(new Edge(e.dest, cost)); } } } return costs; }
  • ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•ด ์ฃผ์–ด์ง„ ๊ธฐ์ ์„ ๊ธฐ์ค€์œผ๋กœ ๊ฐ ์ง€์ ๊นŒ์ง€์˜ ์ตœ์†Œ ๋น„์šฉ์„ ๊ตฌํ•˜๊ณ , ์ด๋ฅผ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class Edge implements Comparable<Edge> { int dest; int weight; public Edge(int dest, int weight) { this.dest = dest; this.weight = weight; } // ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์‚ฌ์šฉ์„ ์œ„ํ•ด ๋น„์šฉ ๊ธฐ์ค€ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ @Override public int compareTo(Edge n) { return this.weight - n.weight; } } // ๊ฐ ์ง€์ ๊นŒ์ง€์˜ ์ตœ์†Œ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•œ๋‹ค. // ์ดํ›„ 1 ~ N๊นŒ์ง€์˜ ์ง€์ ์„ ํ•ฉ์Šน ์ง€์ ์œผ๋กœ ๋‘๊ณ , ์ตœ์†Œ ๋น„์šฉ์„ ๊ตฌํ•œ๋‹ค. class Solution { static ArrayList<Edge>[] adjList; static int n; public int solution(int n, int s, int a, int b, int[][] fares) { this.n = n; init(fares); // S๋ฅผ ๊ธฐ์ ์œผ๋กœ ์ตœ์†Œ ๋น„์šฉ ๊ณ„์‚ฐ int[] startFromSrc = dijkstra(s); // A๋ฅผ ๊ธฐ์ ์œผ๋กœ ์ตœ์†Œ ๋น„์šฉ ๊ณ„์‚ฐ int[] startFromA = dijkstra(a); // B๋ฅผ ๊ธฐ์ ์œผ๋กœ ์ตœ์†Œ ๋น„์šฉ ๊ณ„์‚ฐ int[] startFromB = dijkstra(b); int answer = Integer.MAX_VALUE; for (int i = 1; i <= n; i++) // i๋Š” ํ•ฉ์Šน ์ง€์  // src๋กœ๋ถ€ํ„ฐ i๊นŒ์ง€์˜ ์ตœ์†Œ ๋น„์šฉ + i๋กœ๋ถ€ํ„ฐ a๊นŒ์ง€์˜ ์ตœ์†Œ ๋น„์šฉ + i๋กœ๋ถ€ํ„ฐ b๊นŒ์ง€์˜ ์ตœ์†Œ ๋น„์šฉ answer = Math.min(answer, startFromSrc[i] + startFromA[i] + startFromB[i]); return answer; } // ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ ์ƒ์„ฑ ๋ฐ ์ดˆ๊ธฐํ™” private static void init(int[][] fares) { adjList = new ArrayList[n + 1]; for (int i = 1; i < n + 1; i++) adjList[i] = new ArrayList<>(); for (int[] fare : fares) { adjList[fare[0]].add(new Edge(fare[1], fare[2])); adjList[fare[1]].add(new Edge(fare[0], fare[2])); } } private static int[] dijkstra(int start) { int[] costs = new int[n + 1]; Arrays.fill(costs, Integer.MAX_VALUE); Queue<Edge> queue = new PriorityQueue<>(); queue.add(new Edge(start, 0)); costs[start] = 0; while(!queue.isEmpty()) { Edge node = queue.poll(); int now = node.dest; int weight = node.weight; // ํ˜„์žฌ ๋น„์šฉ๋ณด๋‹ค ๋” ํฐ ๊ฒฝ์šฐ๋Š” ํŒจ์Šค if (weight > costs[now]) continue; // ํ˜„์žฌ ์ •์ ์—์„œ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์—ฃ์ง€ ๋ฆฌ์ŠคํŠธ ArrayList<Edge> edges = adjList[now]; for (Edge e : edges) { // ํ˜„์žฌ(now) ์ •์ ๊นŒ์ง€์˜ ๋น„์šฉ๊ณผ ๋‹ค์Œ์œผ๋กœ ์ด๋™ํ•  ์—ฃ์ง€์˜ ๋น„์šฉ์˜ ํ•ฉ int cost = costs[now] + e.weight; // ์ด์ „ ๋น„์šฉ๋ณด๋‹ค ์ƒˆ๋กœ์šด ๋น„์šฉ์ด ๋” ์ž‘์€ ๊ฒฝ์šฐ ๊ฐฑ์‹  if (cost < costs[e.dest]) { costs[e.dest] = cost; queue.add(new Edge(e.dest, cost)); } } } return costs; } }

โœ๏ธ Review

  • source๊ฐ€ ์ฃผ์–ด์ง€๊ณ , ๊ฐ ์ง€์ ๊นŒ์ง€์˜ ์ตœ์†Œ ๋น„์šฉ์„ ๊ตฌํ•˜๋Š” Single Source Shortest Path ๋ฌธ์ œ๋ผ๋Š” ๊ฒƒ์€ ์‰ฝ๊ฒŒ ์•Œ ์ˆ˜ ์žˆ์—ˆ๊ณ , ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ–ˆ๋‹ค.
  • ๋‹ค๋งŒ, ํ•ฉ์Šน ์ง€์ ์ด๋ผ๋Š” ์กฐ๊ฑด์— ๋Œ€ํ•ด ๋ง‰ํ˜”๋‹ค.

    • S -> X, X -> A, X -> B ์—์„œ X๊ฐ€ 1 ~ N ์ง€์ ์ด ๊ฐ€๋Šฅํ•˜๋‹ค๋Š” ์•„์ด๋””์–ด๊ฐ€ ์ฃผ์š”ํ–ˆ๋‹ค.
@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€